package com.example.javademo.util;

import java.util.Arrays;

/**
 * @Description :
 * @Author 北风
 * @Date Created in 2021/10/8 10:56
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,31,1, 21,2,1,2,4,1,2,3124,564,73,68,54,76};
        int n = nums.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            adjustTree(nums, i, n);
        }

        for (int i = n-1; i > 0; i--) {
            swap(nums, i, 0);
            adjustTree(nums, 0, i);
        }
        System.out.println(Arrays.toString(nums));

    }

    public static void adjustTree(int[] nums, int i, int n) {
        int temp = nums[i];
        for (int j = i * 2 + 1; j < n; j = j * 2 + 1) {
            if (j + 1 < n && nums[j] < nums[j+1]) {
                j ++;
            }
            if (nums[j] > temp) {
                nums[i] = nums[j];
                i = j;
            }
        }
        nums[i] = temp;
    }

    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
